﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <assert.h>
#include<vector>
#include<functional>
#include <iostream>
using namespace std;
namespace Ysz
{



	template <class T, class Container = vector<T>, class Compare = less<T> >

	class priority_queue

	{

	public:

		

		priority_queue()
		{

		}

		template <class InputIterator>

		priority_queue(InputIterator first, InputIterator last)
		{
			for (int i = first; i < last; i++)
			{
				push(*first);
			}
		}

		bool empty() const
		{
			return c.empty();
		}

		size_t size() const
		{
			return c.size();
		}

		const T& top() const
		{
			assert(size());
			return c[0];
		}

		void push(const T& x)
		{
			c.push_back(x);
			adjust_up(size()-1);
		}

		void pop()
		{
			std::swap(c[0], c[size() - 1]);
			c.pop_back();
			adjust_down(0, size());
		}

	private:

		Container c;

		Compare comp;
		void adjust_up(int son)
		{
			int father = (son - 1) / 2;

			while (father >= 0)
			{
				if (comp( c[father],c[son]))
				{
					std::swap(c[son], c[father]);
					son = father;
					father = (son - 1) / 2;
				}
				else
				{
					break;
				}
			}

		}
		void adjust_down(int father , size_t n)
		{
			int son = father * 2 + 1;
			while (son < n)
			{
				if (son + 1 < n && comp(c[son],c[son+1]))
				{
					son++;
				}
				if (comp(c[father], c[son]))
				{
					std::swap(c[son], c[father]);
					father = son;
					son = father * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}


	};

};
